package main

import (
	"math"
	"strconv"
)

func closestCost(baseCosts []int, toppingCosts []int, target int) int {
	res := math.MaxInt32
	memo := map[string]int{}
	for _, cost := range baseCosts {
		tmp := find(toppingCosts, 0, target-cost, memo)
		res = whoClosest(tmp, res)
	}

	return target - res
}

func find(toppingCosts []int, index int, target int, memo map[string]int) int {
	key := strconv.Itoa(target) + "-" + strconv.Itoa(index)
	if c, ok := memo[key]; ok {
		return c
	}

	res := target
	for i := index; i < len(toppingCosts); i++ {
		toppingCost := toppingCosts[i]
		a := find(toppingCosts, i+1, target-toppingCost, memo)
		b := find(toppingCosts, i+1, target-toppingCost*2, memo)
		c := whoClosest(a, b)
		res = whoClosest(res, c)
	}

	memo[key] = res

	return res
}

func whoClosest(a int, b int) int {
	ta := a
	if ta < 0 {
		ta = -ta
	}
	tb := b
	if tb < 0 {
		tb = -tb
	}

	if ta < tb {
		return a
	} else if ta > tb {
		return b
	} else {
		if a < 0 {
			return b
		} else {
			return a
		}
	}
}
